public class Test {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length; // 获取数组长度

        // 置换操作，将每个正数放到对应位置上
        /*比如：将数字1放到数组的第一位（0下标），把2放到数组的第二位（1下标）*/
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // 如果 nums[i] 是正数并且不超过数组长度，并且 nums[i]-1 位置上的数不等于 nums[i]
                // 则交换 nums[i] 和 nums[nums[i]-1] 的位置，直到不能继续交换为止
                /*查看i下标是否为应该放置的数，如果是，则进入下一次循环；如果不是，就将i下标的
                * 数交换到应该去的位置，然后继续判断i下标的数是否合法*/
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        // 遍历数组，找到第一个不满足 nums[i] == i+1 的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                // 返回第一个不满足条件的位置，即为缺失的第一个正数
                return i + 1;
            }
        }

        // 如果数组中的所有正数都出现了，则返回 n+1
        return n + 1;
    }

    public static void main(String[] args) {
        Test test = new Test();
        int res = test.firstMissingPositive(new int[]{3,4,-1,1});
        System.out.println(res);
    }
}
